package com.lfg.leetcode.leetcode0;

import java.util.*;

public class No30FindSubstring {

    public static List<Integer> findSubstring(String s, String[] words) {
        Set<Integer> ret = new HashSet<Integer>();
        if (null == s || "".equals(s) || words.length == 0) {
            return new ArrayList<Integer>(ret);
        }

        Map<String, Integer> data = new HashMap<String, Integer>();
        for (String word : words) {
            data.put(word, data.getOrDefault(word, 0) + 1);
        }

        int sl = s.length();
        int wl = words[0].length();
        int num = words.length;

        int cnt = sl / wl;
        int i1 = sl - wl * num;
        for (int i = 0; i <= i1; i++) {
            Map<String, Integer> tmp = new HashMap<String, Integer>();
            Integer index = null;
            for (int j = 0; j < num; j++) {
                int si = i + wl * j;
                int ei = si + wl;
                if (ei > sl) {
                    break;
                }
                String word = s.substring(si, ei);
                if (!data.containsKey(word)) {
                    break;
                }
                if (index == null) {
                    index = si;
                }
                Integer total = tmp.getOrDefault(word, 0) + 1;
                tmp.put(word, total);
                int need = data.get(word);
                if (total > need) {
                    break;
                }
                if (need == total && tmp.size() == data.size()) {
                    if (checkSize(data, tmp)) {
                        ret.add(index);
                        break;
                    }
                }
            }
        }
        return new ArrayList<Integer>(ret);
    }

    private static boolean checkSize(Map<String, Integer> data, Map<String, Integer> tmp) {
        for (Map.Entry<String, Integer> entry : data.entrySet()) {
            if (!tmp.get(entry.getKey()).equals(entry.getValue())) {
                return false;
            }
        }
        return true;
    }


    public static void main(String[] args) {
//        List<Integer> l = findSubstring("ababaab", new String[]{"ab", "ba", "ba"});
//        List<Integer> l = findSubstring("barfoofoobarthefoobarman" , new String[]{"bar","foo","the"});
//        List<Integer> l = findSubstring("barfoothefoobarman" , new String[]{"foo","bar"});
//        List<Integer> l = findSubstring("wordgoodgoodgoodbestword"  , new String[]{"word","good","best","good"});
        List<Integer> l = findSubstring("abaababbaba", new String[]{"ba", "ab", "ab"});
        System.out.println(l);
//        System.out.println("aaaaaaaaaxxxxxxxx".indexOf("xxx"));


    }
}

